/*********************************************************
          File Name:pisces_dlist.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Wed 29 Apr 2015 03:32:33 PM CST
**********************************************************/

#include "pisces_dlist.h"
#include<string.h>
#include<stdio.h>

void pisces_dlist_init(pisces_dlist_t ** root)
{
    *root = (pisces_dlist_t *) malloc(sizeof(pisces_dlist_t));
    (*root)->index = -1;
    (*root)->pre = *root;
    (*root)->next = *root;
}

void pisces_dlist_insert(pisces_dlist_t ** root, pisces_dlist_t * node)
{
    if (*root == NULL)
        pisces_dlist_init(root);

    node->pre = *root;
    node->next = (*root)->next;
    (*root)->next->pre = node;
    (*root)->next = node;
}

void exchange(pisces_dlist_t ** a, pisces_dlist_t ** b)
{
    pisces_dlist_t *c = NULL;
    size_t size = sizeof(pisces_dlist_t);

    c = (pisces_dlist_t *) malloc(size);
    memcpy(c, *a, size);

    (*a)->item = (*b)->item;
    (*a)->mtime = (*b)->mtime;
    (*a)->st_size = (*b)->st_size;

    (*b)->item = c->item;
    (*b)->mtime = c->mtime;
    (*b)->st_size = c->st_size;
    free(c);
}

static pisces_dlist_t *partition(pisces_dlist_t * s, pisces_dlist_t * e)
{
    pisces_dlist_t *li = s->next;
    int j;

    for (j = s->index; j <= e->index - 1; j++) {
        if (s->mtime <= e->mtime) {
            li = li->pre;
            exchange(&li, &s);
        }
        s = s->pre;
    }
    li = li->pre;
    exchange(&li, &e);
    return li;
}

void pisces_dlist_sort(pisces_dlist_t * s, pisces_dlist_t * e)
{
    pisces_dlist_t *sep;
    if (s->index < e->index) {
        sep = partition(s, e);
        if (sep != s)
            pisces_dlist_sort(s, sep->next);
        if (sep != e)
            pisces_dlist_sort(sep->pre, e);
    }
}

void pisces_dlist_destory(pisces_dlist_t ** root)
{
    pisces_dlist_t *cur, *tmp;

    cur = (*root)->next;
    while (cur->index != -1) {
        tmp = cur->next;
        if (tmp != NULL) {
            free(cur->item);
            free(cur);
            cur = tmp;
        }
    }
    free(*root);
}
